package com.leetcode.algorithm.y20.m12;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * leetcode-cn.com
 * (done)239. 滑动窗口最大值
 * (done)84. 柱状图中最大的矩形
 * 
 * @author jie.deng
 * @date 2020/12/25
 */
public class MySolution1225 {
    
    /**
     * 239. 滑动窗口最大值
     * 
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 
     * 返回滑动窗口中的最大值。
     * 
     * 示例 1：
     * 
     * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
     * 输出：[3,3,5,5,6,7]
     * 解释：
     * 滑动窗口的位置                最大值
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       3
     *  1 [3  -1  -3] 5  3  6  7       3
     *  1  3 [-1  -3  5] 3  6  7       5
     *  1  3  -1 [-3  5  3] 6  7       5
     *  1  3  -1  -3 [5  3  6] 7       6
     *  1  3  -1  -3  5 [3  6  7]      7
     * 示例 2：
     * 
     * 输入：nums = [1], k = 1
     * 输出：[1]
     * 示例 3：
     * 
     * 输入：nums = [1,-1], k = 1
     * 输出：[1,-1]
     * 示例 4：
     * 
     * 输入：nums = [9,11], k = 2
     * 输出：[11]
     * 示例 5：
     * 
     * 输入：nums = [4,-2], k = 2
     * 输出：[4]
     *  
     * 
     * 提示：
     * 
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     * 1 <= k <= nums.length
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * 
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        
        int[] retArr = new int[nums.length - k + 1];

        // queue为单调队列，存储nums的索引的子集，满足以下两条性质：
        // 1.若i<j,则queue[i] < queue[j]；
        // 2.若i<j,则nums[queue[i]] >= nums[queue[j]]。
        Deque<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty()) {
                Integer idx = queue.getLast();
                if (nums[idx] < nums[i]) {
                    queue.removeLast();
                }else {
                    break;
                }
            }
            queue.add(i);

            int retIdx = i - k + 1;
            if (retIdx >= 0) {
                int headIdx = queue.getFirst().intValue();
                retArr[retIdx] = nums[queue.getFirst().intValue()];
                if (retIdx == headIdx) {
                    queue.removeFirst();
                }
            }
        }
        return retArr;
    }
    
    public int[] maxSlidingWindowBak(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        int len = nums.length;
        int[] retArr = new int[len - k + 1];

        // queue为单调队列，存储nums的索引的子集，满足以下两条性质：
        // 1.若0<=i<j<tail,则queue[i] < queue[j]；
        // 2.head<=i<j<tail,则nums[queue[i]] >= nums[queue[j]]。
        int[] queue = new int[len];
        int head = 0;
        int tail = 0;

        for (int i = 0; i < len; i++) {
            // nums[i]入队列，维护单调队列
            int j = tail - 1;
            while (j >= head && nums[queue[j]] < nums[i]) {
                j--;
            }
            tail = j + 1;
            queue[tail++] = i;

            //
            int retIdx = i - k + 1;
            if (retIdx >= 0) {
                retArr[retIdx] = nums[queue[head]];
                if (retIdx == queue[head]) {
                    head++;
                }
            }
        }
        return retArr;
    }
    
    
    /**
     * 
     * 84. 柱状图中最大的矩形
     * 
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * 
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 
     *  
     * 
     * 
     * 
     * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
     * 
     *  
     * 
     * 
     * 
     * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
     * 
     *  
     * 
     * 示例:
     * 
     * 输入: [2,1,5,6,2,3]
     * 输出: 10
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        
        // stack为单调栈，按顺序存储heights的索引的子集，满足以下性质：
        // 若i<j,则heights[stack[i]] <= heights[stack[j]]。
        Deque<Integer> stack = new ArrayDeque<Integer>();

        // r[i]=j表示 heights[i...j] 均不小于 heights[i] && heights[j+1] < heights[i]。
        int[] r = new int[len];
        for (int i = 0; i <= len; i++) {
            while (!stack.isEmpty()) {
                Integer idx = stack.getLast();
                if (i == len || heights[idx] > heights[i]) {
                    stack.removeLast();
                    r[idx] = i - 1;
                } else {
                    break;
                }
            }
            if (i != len) {
                stack.addLast(i);
            }
        }

        // l[i]=j表示 heights[j...i] 均不小于 heights[i] && heights[j-1] < heights[i]。
        int[] l = new int[len];
        for (int i = len - 1; i >= -1; i--) {
            while (!stack.isEmpty()) {
                Integer idx = stack.getLast();
                if (i == -1 || heights[idx] > heights[i]) {
                    stack.removeLast();
                    l[idx] = i + 1;
                } else {
                    break;
                }
            }
            if (i != -1) {
                stack.addLast(i);
            }
        }

        // 计算矩形的最大面积
        int max = 0;
        for (int i = 0; i < len; i++) {
            // heights[i] 表示矩形的高
            // (r[i] - l[i] + 1) 表示矩形的宽
            int area = heights[i] * (r[i] - l[i] + 1);
            max = max > area ? max : area;
        }
        return max;
    }    

}
